Presentación Artículo para Análisis de Datos III

Prof.: Maikol Solís

Estudiante: Jimmy Calvo Monge

II-2021

Artículo de Referencia

• Título: Invariant optimal feature selection: a distance discriminant and feature ranking based solution.
• Autores: J. Liang, S. Yang, A. Winstanley.
• Pattern Recognition 41 (2008) 1429–1439.
• https://doi.org/10.1016/j.patcog.2007.10.018.

Introducción

• El objetivo de este artículo es presentar un nuevo método de selección de variables mediante un ranking de atributos y compararlo con otros métodos en experimentos con varios conjuntos de datos.
• El método propone una medida de ranqueo de variables denominada FSDD, basada en un discriminante de distancias para cada variable.
• Selección de Variables : tiene por seleccionar atributos importantes en un conjunto de datos para mejorar el desempeño de modelos predicitivos para así alcanzar: el alivio de la dimensionalidad y el reforzamiento de la interpretabilidad. Estudiaremos los métodos de ranking de variables.

FSDD

(Feature Selection based on Distance Discriminant)

• Este es el nuevo método que propone nuestro artículo de referencia.

• De acuerdo al artículo: The basis of the proposed algorithm is to find out the features that promise good class separability among different classes as well as make the samples in the same classes as close as possible.

• Para lograr este cometido, se introduce un discriminante de distancias, como un criterio para seleccionar buenas variables.

Este discriminante de distancias está definido incialmente para todo el conjunto de datos y viene dado por:

$$ d_b- \beta d_w $$

Donde $d_b$ (b: between) es un indicador que mide la distancia entre diferentes clases y $d_w$ (w: within) mide la distancia entre las observaciones de una misma clase. El parámetro $\beta$ se utiliza para controlar el impacto de $d_w$

¿Por qué considerar este discriminante de distancias?

Si lo vemos bien es muy natural querer maximizar este indicador: Queremos la mayor distancia entre las clases ($\max d_b$) y al mismo tiempo queremos minimizar la distancia de las observaciones dentro de una misma clase ($\min d_w$).

• Introducimos cierta terminología para explicar estas distancias. Contamos con $N$ observaciones $Y_1,Y_2 \cdots Y_N$ de $n$ variables, de manera que cada $Y_i \in \mathbb{R}^n$, y etiquetadas en $c$ clases distintas.

• Definimos la distancia entre dos puntos $Y_i=(y_i^1, \cdots, y_i^n), Y_j = (y_j^1, \cdots, y_j^n) \in \mathbb{R}^n$ como $$d(Y_i,Y_j)= \sum_{k=1}^n \frac{(y_i^k-y_j^k)^2}{\sigma_k^2}, $$ donde $\sigma_k^2$ es la varianza de la $k$-ésima columna.

• La distancia intra-clase, para la clase $C$ viene dada por

$$ d(C)= \frac{2}{N(N-1)}\sum_{i<j} d(Y_i,Y_j), \quad Y_i,Y_j \in C, $$

y la distancia intra-clase general entonces se define como

$$ d_w = \sum_{i=1}^c \rho_i d(C_i), $$

donde $\rho_i$ es la probabilidad anterior (prior) de la clase $C_i$.

• Por otro lado, la distancia entre clases se define como

$$ d_b= \frac{1}{2}\sum_{i,j} \rho_i \rho_j d(m_i,m_j), $$

donde $m_i$ es el centroide de la clase $C_i$, es decir

$$ m_i= \frac{1}{|Y_\ell \in C_i|} \sum_{Y_\ell \in C_i}Y_\ell. $$

• En el artículo mencionado, se demuestra la fórmula

$$ d_b-\beta d_w= \sum_{k=1}^n \frac{1}{\sigma_k^2} \left[ \sigma_k''^2 - \beta \sum_{i=1}^c \rho_i \sigma_k^2(i) \right] \quad (1) $$

Donde:

• $\sigma_k^2$ es la varianza de la variable $k$-ésima, de todas las observaciones, esto es:

$$ \sigma_k^2= \frac{1}{N} \sum_{i=1}^N (y_i^k - \overline{y_k})^2, \quad \overline{y_k}= \frac{1}{N} \sum_{i=1}^N y_i^k. $$

• $\sigma_k^2(i)$ es la varianza de la variable $k$-ésima, de las observaciones en la clase $i-$ésima, esto es:

$$ \sigma_k^2(i)= \frac{1}{|Y \in C_i|-1} \sum_{Y \in C_i} (y^k - \overline{y_k(i)})^2, \quad \overline{y_k(i)}= \frac{1}{|Y \in C_i|} \sum_{Y \in C_i}y^k. $$

• $\sigma_k''^2$ es la varianza promediada del centroide de la clase $i$-ésima en la variable $k$-ésima. Esto es,

$$ \sigma_k''^2= \sum_{i=1}^c \rho_i (m_i^k -m_k)^2, \quad m_k = \sum_{i=1}^c \rho_i m_i^k. $$

La demostración es un poco extensa y bastante teórica, pero sólo involucra una serie de manipulaciones.

• El método de ranqueo de variables en este caso es utilizando la fórmula $(1)$. Como los términos en la sumatoria de la fórmula dependen de cada variable y el objetivo principal es maximizar la métrica general $d_b- \beta d_w $, entonces los autores argumentan que, en cierto sentido, las mejores $m$ variables son las $m$ primeras variables con mayor valor en la métrica

$$ \text{FSDD}(k)= \frac{1}{\sigma_k^2} \left[\sigma_k''^2 - \beta \sum_{i=1}^c \rho_i \sigma_k^2(i) \right] $$

Y esta es la métrica para ranquear las variables que se propone en este artículo. Es un indicador por variable y depende de la naturaleza del conjunto de datos, y no de ningún modelo en particular (filter).

Metodología

Para comparar la eficacia del método de selección de variables FSDD el artículo propone comparar el algoritmo FSDD contra otros dos algoritmos establecidos de selección de variables que son

• Algoritmo ReliefF

• Uso del criterio de información mutua mediante el algoritmo mrmrMID.

Éstos dos algoritmos filter han sido ampliamente utilizados para la selección de variables. En el reporte del artículo se puede encontrar lo que hacen estos algoritmos específicamente, por falta de tiempo no entraremos en estos detalles.

😉

El experimento hace lo siguiente:

• Se tienen varios conjuntos de datos de muestra. Para cada uno se selecciona un subconjunto de datos con las mejores $m$ variables de acuerdo a los tres algoritmos (FSDD, ReliefF, mrmrMID).

• Sobre el subconjunto de datos se aplica un clasificador (KNN, NB, DT y SVM) y se mide su precisión.

• Esto se hace para cada $m=1$ hasta $m = $ #columnas.
• En un gráfico se comparan las precisiones obtenidas con cada método de selección de variables.

Los conjuntos de datos utilizados en el artículo de referencia sobre el valor FSDD son los siguientes:

1. MFeat (Multiple Features Dataset)
2. Satimage
3. Spambase
4. Spectrometer
5. Wine
6. Analcatdata
7. Iris
8. Vowel

Todos, excepto Analcatdata que está en Statlib, se encuentran en el repositorio UCI, de libre acceso y descarga. Para este trabajo decidí utilizar sólo los que siguen, por cuestiones de tiempo y duración de algunos de los algoritmos.

1. MFeat
2. Satimage
3. Spambase
4. Wine

En la siguiente tabla se encuentra la información sobre el tamaño de cada uno de estos conjuntos de datos y el método de CV a utilizar de acuerdo al artículo.

   

Conjunto de Datos	#Variables	#Instancias	CV Fold
Mfeat	649	2000	2-Fold CV
Satimage	36	6435	2-Fold CV
Spambase	57	4601	2-Fold CV
Wine	13	178	10-Fold CV

   

Descargué los conjuntos de datos como csv y en las siguientes líneas de código los leo para el análisis. El conjunto Mfeat se puede descargar desde $\verb"mklearn"$, sin embargo requiere de cierta preparación porque viene un poco fragmentado.

• En los artículos no viene referencia a alguna biblioteca o repositorio en donde se encuentren estos métodos o experimentos, o no lo pude encontrar. Los autores mencionan que implementaron el análisis en Matlab.

  😕

• Por eso, para replicar los experimentos, decidí emular el análisis en python, por comodidad.

• Todo el código se puede encontrar aquí:

Resultados de los experimentos del artículo

Siguiendo la metodología propuesta, los autores presentan los resultados de sus experimentos en gráfocos como los que siguen. Aquí se puede apreciar la ventaja en precisión que ofrece el método propuesto en comparación a los otros dos. En este caso se muestran los resultados para el conjunto de datos Satimage.

Similarmente, los siguientes son los resultados obtenidos por los autores para el conjunto Mfeat:

Los siguientes son los resultados obtenidos por los autores para el conjunto Spambase:

También se presentan algunas tablas de precisión, en lugar de gráficos, para algunos otros conjuntos de datos. Cada tabla muestra en esencia los resultados que antes, para cada $m$ se muestra la precisión obtenida con cada clasificador al filtrar el conjunto de datos usando cada algoritmo estudiado. Aquí la tabla para el conjunto de datos $\verb"Wine"$.

Resultados de mis experimentos

Se intentó programar los pseudo códigos tal y como se han especificado en los artículos (Excepto el de ReliefF, para el cual se usó una biblioteca). De mi parte creo que la implementación que he hecho en python sigue al pie de la letra lo escrito en los artículos. Comparemos los resultados obtenidos con mi implementación con los originales. 😅

Cualquiera puede acceder al github y darme su opinión en qué se puede reforzar el código 😊

Estos son los gráficos que obtuve al aplicar el mismo proceso al conjunto de datos $\verb"Satimage"$, usando la implementación en python que hice. 🤓

Los siguientes son los gráficos que obtuve para el conjunto Mfeat.

Seguidamente los resultados de la réplica para Spambase

Finalmente, ésta fue la tabla de precisiones obtenida en la réplica para el conjunto $\verb"Wine"$.

Problemas y Limitaciones

• Los artículos no brindaban referencias para accesar al código original que fue usado por los autores 😢

• Se menciona que la implementación fue hecha en matlab. Por esta razón se recurrió a una implementación en python, que puede tener errores o aspectos que no he considerado todavía. Es muy probable que esto haya afectado los resultados. De hecho existen algunos hiperparámetros en el método ReliefF de python que no se pueden controlar, como el número de vecinos a seleccionar en cada iteración. Por falta de tiempo no se implementó este método y en su lugar se utilizó una biblioteca de python hecha para éste.

Conclusiones

• La motivación teórica detrás de la definición de la métrica FSDD es muy intuitiva y la fórmula desarrollada por los autores permite obtener una nueva métrica para calificar variables dentro del problema de clasificación planteado.

• A pesar de no contar con la implementación explícita realizada por los autores, se logró emular el código apropiado siguiendo las descripciones de los algoritmos hechas en la bibliografía. Por detalles del software utilizado en algunos casos los experimentos efectuados originalmente no se han podido emular con exactitud, aunque esto también es razonable debido a la diferencia desde el punto de vista del software empleado.

• A pesar de esta limitación, los resultados obtenidos en este proyecto muestran un desempeño relativamente superior de la métrica FSDD en muchas instancias, y en el peor de los casos las tres métricas terminan siendo equivalentes con respecto al objetivo de precisión.

Bibliografía

• Artículo de Referencia:

  • J.Liang, S.Yang, A.Winstanley, Invariant optimal feature selection: a distance discriminant and feature ranking based solution, Pattern Recognition 41 (2008) 1429–1439.

• Otros artículos utilizados en este trabajo:

  • Jimin Lee, Nomin Batnyam, Sejong Ohn, RFS: Efficient feature selection method based on R-value. Comp. in Bio. and Med. 43, Issue 2, (2013) 91–99.

  • C.Ding, H.Peng, Minimum redundancy feature selection from microarray gene expression data. Proceedings of the IEEE Computer Society, Conference on Bioinformatics, IEEE Computer Society, 2003, p.523.

  • J.Liang, S.Yang, A.Winstanley, Invariant optimal feature selection: a distance discriminant and feature ranking based solution, Pattern Recognition 41 (2008) 1429–1439.

  • M.Robnik-Sikonja, I.Kononenko, Theoretical and empirical analysis of ReliefF and RReliefF, Mach.Learn. 53 (2003) 23–69.

Apéndice:

Originalmente iba a considerar este artículo para la exposición:

• RFS: Efficient feature selection method based on R-value. Jimin Lee, Nomin Batnyam, Sejong Ohn. Computers in Biology and Medicine, Volume 43, Issue 2, February, 2013 pp 91–99. https://doi.org/10.1016/j.compbiomed.2012.11.010.

En este se desarrollaba una nueva técnica de filtro de variables, llamada el valor R. Allí se comparaba esta métrica con las que he presentado aquí: FSDD, ReliefF y mrmrMID. Entonces tuve que buscar el artículo actual, en el que se introduce la métrica FSDD:

• Invariant optimal feature selection: a distance discriminant and feature ranking based solution. J.Liang, S.Yang, A.Winstanley. Pattern Recognition 41 (2008) 1429–1439. https://doi.org/10.1016/j.patcog.2007.10.018.

• Y en este se compara la métrica FSDD versus el uso de ReliefF y mrmrMID.

• No utilicé el artículo del valor R porque no pude conseguir los conjuntos de datos que venían allí (eran más que todo conjuntos de micro-array data). Además con éste tendría que referenciar varios artículos hacia atrás (el de FSDD, el de mrmrMID, ...). Por eso decidí sólo usar el artículo de FSDD.

• La técnica del valor R es muy sencilla y se basa en el área de traslape de distintas clases para una cada variable. El artículo aserta que, a pesar de su simplicidad, puede dar mejores (o similares) resultados que las otras métricas en muchos casos.

• A continuación el lector puede observar la implementación del mismo y notar la simplicidad de la calificación para cada variable.

• Pseudo-código. La siguiente función calcula el valor $R$ de un atributo en particular. Los hiperparámetros de este algoritmo son: $K$: la cantidad de vecinos cercanos a seleccionar y $\theta$: un valor de corte (threshold).

Input: Un vector $V$ que es la columna de un atributo en un conjunto de datos, y un vector $C$ de clases para cada observación en $V$.
Output: valor $R$ del atributo en cuestión.
1. Inicializar $OV[]$. Vector para almacenar si $V[i]$ está en área de traslape o no.
2. Ordenar $V[]$ y $C[]$ de manera que se conserve la correspondencia de clases. 3. $N$: longitud de $V[]$. 4. $Y=0$. 5. Para cada $V[i]$ hacer:
3.     Encuentre los $k$ valores más cercanos a $V[i]$ y guárdelos en $KNV[i]$
4.     Como $V[]$ está ordenado, éstos son $V[i-k:i+k]$
5.     Cuente el número de elementos de $KNV[i]$ que no tienen la clase $C[i]$, esto es $X$.
6.     Si $X/K>\theta$:
7.       $OV[i]=1$
8.     Si no, entonces:
9.       $OV[i]=0$
10. Sume los valores de $OV[]$, esto es $Y$.
11. Regresar: $Y/N$.

• Esta implementación también se encuentra en el notebook del repositorio de Github que compartí más arriba

• En este repositorio también están los archivos pdf de todos los artículos usados para la referencia.

---